package ch4.part4;

import java.util.Arrays;

/**
 * 堆排序，不稳定排序
 * 平均时间复杂度：O(n) = nlogn
 * 最坏时间复杂度：O(n) = nlogn
 * 空间复杂度：O(n) = 1
 *
 * @author liuwanxiang
 * @version 2019/06/15
 */
public class HeapSort {

    private static void sort(int[] array) {
        // 1. 构建最大二叉堆，此时还并不是有序数组
        for (int i = array.length >> 1; i >= 0; i--) {
            downAdjust(array, i, array.length - 1);
        }
        System.out.println(Arrays.toString(array));

        // 2. 循环对二叉堆的堆顶元素进行 "删除"
        for (int i = array.length-1; i > 0; i--) {
            // 最大值放在堆数组的最后，模拟删除
            int tempData = array[i];
            array[i] = array[0];
            array[0] = tempData;
            // 剩余的其他元素，构建堆顶
            downAdjust(array,0,i);
        }

    }

    private static void downAdjust(int[] array, int parentIndex, int len) {
        int tempData = array[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < len) {
            if (childIndex + 1 < len && array[childIndex + 1] < array[childIndex]) {
                childIndex++;
            }
            if (tempData <= array[childIndex]) {
                break;
            }
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }
        array[parentIndex] = tempData;
    }

    public static void main(String[] args) {
        int[] array = {1, 0, 9, 2, 3, 8, 7, 4, 6, 5};
        sort(array);
        System.out.println(Arrays.toString(array));
    }

}
